

class TreeNode:
    """二叉树节点类"""
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    """二叉树类"""
    def __init__(self, root_value=None):
        if root_value is not None:
            self.root = TreeNode(root_value)
        else:
            self.root = None
    
    def insert(self, value):
        """按层级顺序插入节点"""
        if self.root is None:
            self.root = TreeNode(value)
            return
        
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            
            if node.left is None:
                node.left = TreeNode(value)
                return
            else:
                queue.append(node.left)
            
            if node.right is None:
                node.right = TreeNode(value)
                return
            else:
                queue.append(node.right)
    
    def search(self, value):
        """广度优先搜索"""
        if self.root is None:
            return False
        
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            if node.value == value:
                return True
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return False
    
    def preorder_traversal(self, node):
        """前序遍历：根->左->右"""
        if node is None:
            return []
        return [node.value] + self.preorder_traversal(node.left) + self.preorder_traversal(node.right)
    
    def inorder_traversal(self, node):
        """中序遍历：左->根->右"""
        if node is None:
            return []
        return self.inorder_traversal(node.left) + [node.value] + self.inorder_traversal(node.right)
    
    def postorder_traversal(self, node):
        """后序遍历：左->右->根"""
        if node is None:
            return []
        return self.postorder_traversal(node.left) + self.postorder_traversal(node.right) + [node.value]
    
    def level_order_traversal(self):
        """层级遍历"""
        if self.root is None:
            return []
        
        result = []
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            result.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return result
    
    def height(self, node):
        """计算树的高度"""
        if node is None:
            return 0
        return 1 + max(self.height(node.left), self.height(node.right))
    
    def __str__(self):
        """可视化二叉树"""
        if self.root is None:
            return "Empty Tree"
        
        lines = []
        level = [self.root]
        while level:
            current_line = []
            next_level = []
            
            for node in level:
                if node:
                    current_line.append(str(node.value))
                    next_level.append(node.left)
                    next_level.append(node.right)
                else:
                    current_line.append(" ")
            
            if any(node is not None for node in next_level):
                lines.append(" ".join(current_line))
            level = next_level
        
        return "\n".join(lines)

    def get_root(self):
        return self.root
    

# 测试代码
if __name__ == "__main__":
    # 创建二叉树
    tree = BinaryTree(1)
    tree.insert(2)
    tree.insert(3)
    tree.insert(4)
    tree.insert(5)
    tree.insert(6)
    tree.insert(7)
    
    # 打印树结构
    print("树结构:")
    print(tree)
    print(tree.level_order_traversal())
    root = tree.get_root()
    print(root.value)
    print(root.left.value, root.right.value)
    print(root.left.left.value,root.left.right.value, root.right.left.value, root.right.right.value)
    
    # 遍历测试
    print("\n前序遍历:", tree.preorder_traversal(tree.root))
    print("中序遍历:", tree.inorder_traversal(tree.root))
    print("后序遍历:", tree.postorder_traversal(tree.root))
    print("层级遍历:", tree.level_order_traversal())
    
    # 搜索测试
    print("\n搜索节点:")
    print("4 是否在树中:", tree.search(4))
    print("8 是否在树中:", tree.search(8))
    
    # 树高度
    print("\n树的高度:", tree.height(tree.root))